home *** CD-ROM | disk | FTP | other *** search
/ MacGames Sampler / PHT MacGames Bundle.iso / MacSource Folder / Samples from the CD / C and C++ / GIF source / GIFstuff⁄gifcompr.c < prev    next >
Text File  |  1989-05-25  |  11KB  |  423 lines
  1. /***************************************************************************
  2.  *
  3.  *  GIFENCOD.C       - GIF Image compression routines
  4.  *
  5.  *  Lempel-Ziv compression based on 'compress'.  GIF modifications by
  6.  *  David Rowley (mgardi@watdcsu.waterloo.edu)
  7.  *
  8.  ***************************************************************************/
  9.  
  10. /*
  11.  * General DEFINEs
  12.  */
  13. #define min(a,b)        ((a>b) ? b : a)
  14.  
  15. #define BITS    12
  16. #define MSDOS   1
  17.  
  18. #define HSIZE  5003            /* 80% occupancy */
  19.  
  20. /*
  21.  * Pointer to function returning an int
  22.  */
  23. typedef int (* ifunptr)();
  24.  
  25. /*
  26.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  27.  */
  28. typedef int             code_int;
  29.  
  30. #ifdef SIGNED_COMPARE_SLOW
  31. typedef unsigned long int count_int;
  32. typedef unsigned short int count_short;
  33. #else
  34. typedef long int          count_int;
  35. #endif
  36.  
  37. #ifdef NO_UCHAR
  38.  typedef char   char_type;
  39. #else
  40.  typedef        unsigned char   char_type;
  41. #endif /* UCHAR */
  42.  
  43. /*
  44.  *
  45.  * GIF Image compression - modified 'compress'
  46.  *
  47.  * Based on: compress.c - File compression ala IEEE Computer, June 1984.
  48.  *
  49.  * By Authors:  Spencer W. Thomas       (decvax!harpo!utah-cs!utah-gr!thomas)
  50.  *              Jim McKie               (decvax!mcvax!jim)
  51.  *              Steve Davies            (decvax!vax135!petsd!peora!srd)
  52.  *              Ken Turkowski           (decvax!decwrl!turtlevax!ken)
  53.  *              James A. Woods          (decvax!ihnp4!ames!jaw)
  54.  *              Joe Orost               (decvax!vax135!petsd!joe)
  55.  *
  56.  */
  57. #include <stdio.h>
  58. #include <ctype.h>
  59. #include <signal.h>
  60.  
  61. #define ARGVAL() (*++(*argv) || (--argc && *++argv))
  62.  
  63. static int n_bits;                        /* number of bits/code */
  64. static int maxbits = BITS;                /* user settable max # bits/code */
  65. static code_int maxcode;                  /* maximum code, given n_bits */
  66. static code_int maxmaxcode = (code_int)1 << BITS; /* should NEVER generate this
  67. code */
  68. #ifdef COMPATIBLE               /* But wrong! */
  69. # define MAXCODE(n_bits)        ((code_int) 1 << (n_bits) - 1)
  70. #else
  71. # define MAXCODE(n_bits)        (((code_int) 1 << (n_bits)) - 1)
  72. #endif /* COMPATIBLE */
  73.  
  74. static count_int htab [HSIZE];
  75. static unsigned short codetab [HSIZE];
  76. #define HashTabOf(i)       htab[i]
  77. #define CodeTabOf(i)    codetab[i]
  78.  
  79. static code_int hsize = HSIZE;                 /* for dynamic table sizing */
  80. static count_int fsize;
  81.  
  82. /*
  83.  * To save much memory, we overlay the table used by compress() with those
  84.  * used by decompress().  The tab_prefix table is the same size and type
  85.  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
  86.  * get this from the beginning of htab.  The output stack uses the rest
  87.  * of htab, and contains characters.  There is plenty of room for any
  88.  * possible stack (stack used to be 8000 characters).
  89.  */
  90.  
  91. #define tab_prefixof(i) CodeTabOf(i)
  92. #define tab_suffixof(i)        ((char_type *)(htab))[i]
  93. #define de_stack               ((char_type *)&tab_suffixof((code_int)1<<BITS))
  94.  
  95. static code_int free_ent = 0;                  /* first unused entry */
  96. static int exit_stat = 0;
  97.  
  98. /*
  99.  * block compression parameters -- after all codes are used up,
  100.  * and compression rate changes, start over.
  101.  */
  102. static int clear_flg = 0;
  103.  
  104. static int offset;
  105. static long int in_count = 1;            /* length of input */
  106. static long int out_count = 0;           /* # of codes output (for debugging) */
  107.  
  108. /*
  109.  * compress stdin to stdout
  110.  *
  111.  * Algorithm:  use open addressing double hashing (no chaining) on the
  112.  * prefix code / next character combination.  We do a variant of Knuth's
  113.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  114.  * secondary probe.  Here, the modular division first probe is gives way
  115.  * to a faster exclusive-or manipulation.  Also do block compression with
  116.  * an adaptive reset, whereby the code table is cleared when the compression
  117.  * ratio decreases, but after the table fills.  The variable-length output
  118.  * codes are re-sized at this point, and a special CLEAR code is generated
  119.  * for the decompressor.  Late addition:  construct the table according to
  120.  * file size for noticeable speed improvement on small files.  Please direct
  121.  * questions about this implementation to ames!jaw.
  122.  */
  123.  
  124. static int g_init_bits;
  125. static FILE *g_outfile;
  126.  
  127. static int ClearCode;
  128. static int EOFCode;
  129.  
  130. compress( init_bits, outfile, ReadValue )
  131. int init_bits;
  132. FILE *outfile;
  133. ifunptr ReadValue;
  134. {
  135.     register long fcode;
  136.     register code_int i = 0;
  137.     register int c;
  138.     register code_int ent;
  139.     register code_int disp;
  140.     register code_int hsize_reg;
  141.     register int hshift;
  142.  
  143.     /*
  144.      * Set up the globals:  g_init_bits - initial number of bits
  145.      *                      g_outfile   - pointer to output file
  146.      */
  147.     g_init_bits = init_bits;
  148.     g_outfile = outfile;
  149.  
  150.     /*
  151.      * Set up the necessary values
  152.      */
  153.     offset = 0;
  154.     out_count = 0;
  155.     clear_flg = 0;
  156.     in_count = 1;
  157.     maxcode = MAXCODE(n_bits = g_init_bits);
  158.  
  159.     ClearCode = (1 << (init_bits - 1));
  160.     EOFCode = ClearCode + 1;
  161.     free_ent = ClearCode + 2;
  162.  
  163.     char_init();
  164.  
  165.     ent = GIFNextPixel( ReadValue );
  166.  
  167.     hshift = 0;
  168.     for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
  169.         hshift++;
  170.     hshift = 8 - hshift;                /* set hash code range bound */
  171.  
  172.     hsize_reg = hsize;
  173.     cl_hash( (count_int) hsize_reg);            /* clear hash table */
  174.  
  175.     output( (code_int)ClearCode );
  176.  
  177. #ifdef SIGNED_COMPARE_SLOW
  178.     while ( (c = GIFNextPixel( ReadValue )) != (unsigned) EOF ) {
  179. #else
  180.     while ( (c = GIFNextPixel( ReadValue )) != EOF ) {
  181. #endif
  182.  
  183.         in_count++;
  184.  
  185.         fcode = (long) (((long) c << maxbits) + ent);
  186.         i = (((code_int)c << hshift) ~ ent);    /* xor hashing */
  187.  
  188.         if ( HashTabOf (i) == fcode ) {
  189.             ent = CodeTabOf (i);
  190.             continue;
  191.         } else if ( (long)HashTabOf (i) < 0 )      /* empty slot */
  192.             goto nomatch;
  193.         disp = hsize_reg - i;           /* secondary hash (after G. Knott) */
  194.         if ( i == 0 )
  195.             disp = 1;
  196. probe:
  197.         if ( (i -= disp) < 0 )
  198.             i += hsize_reg;
  199.  
  200.         if ( HashTabOf (i) == fcode ) {
  201.             ent = CodeTabOf (i);
  202.             continue;
  203.         }
  204.         if ( (long)HashTabOf (i) > 0 )
  205.             goto probe;
  206. nomatch:
  207.         output ( (code_int) ent );
  208.         out_count++;
  209.         ent = c;
  210. #ifdef SIGNED_COMPARE_SLOW
  211.         if ( (unsigned) free_ent < (unsigned) maxmaxcode) {
  212. #else
  213.         if ( free_ent < maxmaxcode ) {
  214. #endif
  215.             CodeTabOf (i) = free_ent++; /* code -> hashtable */
  216.             HashTabOf (i) = fcode;
  217.         } else
  218.                 cl_block();
  219.     }
  220.     /*
  221.      * Put out the final code.
  222.      */
  223.     output( (code_int)ent );
  224.     out_count++;
  225.     output( (code_int) EOFCode );
  226.  
  227.     return;
  228. }
  229.  
  230. /*****************************************************************
  231.  * TAG( output )
  232.  *
  233.  * Output the given code.
  234.  * Inputs:
  235.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  236.  *              that n_bits =< (long)wordsize - 1.
  237.  * Outputs:
  238.  *      Outputs code to the file.
  239.  * Assumptions:
  240.  *      Chars are 8 bits long.
  241.  * Algorithm:
  242.  *      Maintain a BITS character long buffer (so that 8 codes will
  243.  * fit in it exactly).  Use the VAX insv instruction to insert each
  244.  * code in turn.  When the buffer fills up empty it and start over.
  245.  */
  246.  
  247. static unsigned long cur_accum = 0;
  248. static int  cur_bits = 0;
  249.  
  250. static
  251. unsigned long masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F,
  252.                                   0x001F, 0x003F, 0x007F, 0x00FF,
  253.                                   0x01FF, 0x03FF, 0x07FF, 0x0FFF,
  254.                                   0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
  255.  
  256. static
  257. output( code )
  258. code_int  code;
  259. {
  260.     cur_accum &= masks[ cur_bits ];
  261.  
  262.     if( cur_bits > 0 )
  263.         cur_accum |= ((long)code << cur_bits);
  264.     else
  265.         cur_accum = code;
  266.  
  267.     cur_bits += n_bits;
  268.  
  269.     while( cur_bits >= 8 ) {
  270.         char_out( (unsigned int)(cur_accum & 0xff) );
  271.         cur_accum >>= 8;
  272.         cur_bits -= 8;
  273.     }
  274.  
  275.     /*
  276.      * If the next entry is going to be too big for the code size,
  277.      * then increase it, if possible.
  278.      */
  279.    if ( free_ent > maxcode || clear_flg ) {
  280.  
  281.             if( clear_flg ) {
  282.  
  283.                 maxcode = MAXCODE (n_bits = g_init_bits);
  284.                 clear_flg = 0;
  285.  
  286.             } else {
  287.  
  288.                 n_bits++;
  289.                 if ( n_bits == maxbits )
  290.                     maxcode = maxmaxcode;
  291.                 else
  292.                     maxcode = MAXCODE(n_bits);
  293.             }
  294.         }
  295.  
  296.     if( code == EOFCode ) {
  297.         /*
  298.          * At EOF, write the rest of the buffer.
  299.          */
  300.         while( cur_bits > 0 ) {
  301.                 char_out( (unsigned int)(cur_accum & 0xff) );
  302.                 cur_accum >>= 8;
  303.                 cur_bits -= 8;
  304.         }
  305.  
  306.         flush_char();
  307.  
  308.         fflush( g_outfile );
  309.  
  310.         if( ferror( g_outfile ) )
  311.                 writeerr();
  312.     }
  313. }
  314.  
  315. /*
  316.  * Clear out the hash table
  317.  */
  318. static
  319. cl_block ()             /* table clear for block compress */
  320. {
  321.  
  322.         cl_hash ( (count_int) hsize );
  323.         free_ent = ClearCode + 2;
  324.         clear_flg = 1;
  325.  
  326.         output( (code_int)ClearCode );
  327. }
  328.  
  329. static
  330. cl_hash(hsize)          /* reset code table */
  331. register count_int hsize;
  332. {
  333.  
  334.         register count_int *htab_p = htab+hsize;
  335.  
  336.         register long i;
  337.         register long m1 = -1;
  338.  
  339.         i = hsize - 16;
  340.         do {                            /* might use Sys V memset(3) here */
  341.                 *(htab_p-16) = m1;
  342.                 *(htab_p-15) = m1;
  343.                 *(htab_p-14) = m1;
  344.                 *(htab_p-13) = m1;
  345.                 *(htab_p-12) = m1;
  346.                 *(htab_p-11) = m1;
  347.                 *(htab_p-10) = m1;
  348.                 *(htab_p-9) = m1;
  349.                 *(htab_p-8) = m1;
  350.                 *(htab_p-7) = m1;
  351.                 *(htab_p-6) = m1;
  352.                 *(htab_p-5) = m1;
  353.                 *(htab_p-4) = m1;
  354.                 *(htab_p-3) = m1;
  355.                 *(htab_p-2) = m1;
  356.                 *(htab_p-1) = m1;
  357.                 htab_p -= 16;
  358.         } while ((i -= 16) >= 0);
  359.  
  360.         for ( i += 16; i > 0; i-- )
  361.                 *--htab_p = m1;
  362. }
  363.  
  364. static
  365. writeerr()
  366. {
  367.         printf( "error writing output file\n" );
  368.         exit(1);
  369. }
  370.  
  371. /******************************************************************************
  372.  *
  373.  * GIF Specific routines
  374.  *
  375.  ******************************************************************************/
  376.  
  377. /*
  378.  * Number of characters so far in this 'packet'
  379.  */
  380. static int a_count;
  381.  
  382. /*
  383.  * Set up the 'byte output' routine
  384.  */
  385. static
  386. char_init()
  387. {
  388.         a_count = 0;
  389. }
  390.  
  391. /*
  392.  * Define the storage for the packet accumulator
  393.  */
  394. static char accum[ 256 ];
  395.  
  396. /*
  397.  * Add a character to the end of the current packet, and if it is 254
  398.  * characters, flush the packet to disk.
  399.  */
  400. static
  401. char_out( c )
  402. int c;
  403. {
  404.         accum[ a_count++ ] = c;
  405.         if( a_count >= 254 )
  406.                 flush_char();
  407. }
  408.  
  409. /*
  410.  * Flush the packet to disk, and reset the accumulator
  411.  */
  412. static
  413. flush_char()
  414. {
  415.         if( a_count > 0 ) {
  416.                 fputc( a_count, g_outfile );
  417.                 fwrite( accum, 1, a_count, g_outfile );
  418.                 a_count = 0;
  419.         }
  420. }
  421.  
  422. /* The End */
  423.